package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/28 20:18
 */
public class _493_2 {
    public static int reversePairs(int[] nums) {
        int[] buffer = new int[nums.length / 2 + 1];
        return reversePairs(nums, buffer, 0, nums.length - 1);
    }

    private static int reversePairs(int[] nums, int[] buffer, int left, int right) {
        if (right <= left) {
            return 0;
        }
        int count = 0;
        int mid = (left + right) / 2;
        int leftPlus = reversePairs(nums, buffer, left, mid);
        int rightPlus = reversePairs(nums, buffer, mid + 1, right);
        count += leftPlus + rightPlus;



        //从2个数据/3个数据开始计算
        //得到这次遍历的返回值
        int i = left;
        int j = mid + 1;
        int add = 0;

        while (i <= mid) {
            while (j <= right && nums[i] > nums[j] * 2L) {
                j++;
            }
            add += j - mid - 1;
            i++;
        }
        count += add;

        //连接本次遍历内容的左右部分。左右部分相对顺序，而单独的左部分和右部分不一定顺序
        System.arraycopy(nums, left, buffer, 0, mid - left + 1);
        i = 0;
        int bright = mid - left;
        j = mid + 1;
        int k = left;
        while (i <= bright && j <= right) {
            if (buffer[i] < nums[j]) {
                nums[k++] = buffer[i++];
            } else {
                nums[k++] = nums[j++];
            }
        }
        while (i <= bright) {
            nums[k] = buffer[i];
            k++;
            i++;
        }
        return count;
    }
}
